package com.learn.algorithm.graph;

import java.util.ArrayList;

public class LeetCode210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 初始化邻接表图
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        int[] indegree = new int[numCourses];
        for (int[] edge : prerequisites) {
            // edge[0] 依赖 edge[1] 有向图表示就是存在edge[1] -> edge[0]的边
            // 邻接表中添加边edge[1] -> edge[0]
            graph.get(edge[1]).add(edge[0]);
            // edge[0]的入度加1
            indegree[edge[0]]++;
        }
        int[] queue = new int[numCourses];
        int l = 0, r = 0;
        for (int i = 0; i < numCourses; i++) {
            // 收集入度为0的课程直接加入结果中
            if (indegree[i] == 0) {
                queue[r++] = i;
            }
        }
        int cnt = 0;
        while (l < r) {
            cnt++;
            // 队列不空的时候, 从队列头部拿一个节点(注意到该节点的入度为0)
            int cur = queue[l++];
            //  一旦该节点的邻居的入度为0了 将该入度为0的邻居加到结果
            for (int next : graph.get(cur)) {
                if (--indegree[next] == 0) {
                    queue[r++] = next;
                }
            }
        }
        return cnt == numCourses ? queue : new int[0];
    }
}
